////////////////////////////////////////////////////////////////////////////////
/*!	\file		C45Generator.hpp
**	\brief		Declares the C45Generator class.
**	\author		Nate Cleveland
**	\date		11/18/2002 6:21:08 PM
**	\par		DESCRIPTION:
				This class is a function object that generates a Decision Tree for the 
				 passed in class. Please refer to C45.hpp for an explanasion of some 
				 terminology used in this documentation. Terms like "Cases" and 
				 "Classes" have special meaning when refering to Decision Trees. Also 
				 see Node.hpp for details on node traversal logic.



	\par		ALGORITHMS:
				The techniques used for generating this tree are in many ways influenced 
				 by J. Ross Quinlan and his book C4.5: Programs for Machine Learning. The 
				 general algorithm used to generate the Tree is as follows
					
					- Select the most frequent class.
					- Evaluate all cases in relation to the most frequent class.
					- Select the case with the most info gain.
					- Divide the examples into those that return true in relation to the 
					selected case, these will be passed to the left child. Any that are 
					false are sent to the right child.
					- Recurse along each child.
					- Naturally, in several places we test to see if we are a Leaf rather 
					then a Branch. If this node is a Leaf it is set accordingly.
					
					
	\par
				There are some places where this TreeGenerator deviates from the standard 
				 laid down by Quinlan. They are detailed below.
					- The InfoGain of a node is used over TreeInfoGain for selecting the 
					base Case. It was found during testing that this only complicates 
					the fully grown tree and produced far too many bugs to be worth the 
					computation.
					- At this time the tree is not translated into rule-sets. This is 
					considered a potential boost in performance that is scheduled to be 
					added at a later time.
					- All values in the training examples are left as continuous values 
					in this Decision Tree implementation. However, they are parsed to 
					see if they could be interpreted as boolean true/false. This was 
					added during initial testing when it was found that the C45 tree 
					could not learn AND without translating the continuous values to 
					true/false.
					
	\par	
				This TreeGenerator still follow C4.5 completely in the following areas.
					- All formulas presented in C4.5 are left intact and unaltered. Even 
					if some of them (TreeInfoGain) are ignored.
					- Unlike ID3 and most other Decision Tree algorithms this algorithm 
					follows C4.5 and does not average the boundary breaking apart 
					continuous sequences. Instead the midpoint is computed but the first 
					value greater then or equal to the midpoint is set as the boundary. 
					In this way C4.5 ensures that the selected value is found within the 
					example set.
					- The traversing algorithm does not know if the next node is a leaf 
					or until it visits it. This does use more memory then other 
					implementations while allowing the algorithm to have more then two 
					Classes in each tree.
					- No optimizations are computed while the tree is growing. Only 
					after it is finished are optimizations considered. (Note, at this
					time no optimizations are used).



	\par		TEMPLITIZATION:
				 The C45Generator class has been templitized which maximizes generality
				  while perserving a clean coding structure. C45Generators template 
				  paramaters are as follows.
					- RefObj_type. This is the type of object that the C45Generator will
					store a reference of in its ctor.
					- Adapter. The adapter is the workhorse that provides the flexibility 
					needed to templitize C45Generator. Therefore, the object passed in
					as the Adapter must contain the following typedefs and methods. 
					
						* typedefs 
							- myRefClass
							- Class_type
							- Case_type
							- Example_type
							- Node_type

						* methods (all must be public, static and inline).
							- float			GetCaseValue(const Case_type& Case)
								* Returns to caller the floating point value of this case.

							- Class_type		GetExampleResult(Example_type ex)
								* Returns to caller the result of this example.

							- Node_type&	GetTreeRootRef(myRefClass& myRef)
								* Returns to the caller a reference to the root node.

							- Node_type*	GetTreeRootPtr(myRefClass& myRef)
								* Returns to the caller a pointer to the root node.

							- Node_type**	GetTreeRootPtrPtr(myRefClass& myRef)
								* Returns to the caller a pointer-pointer to the root node.

							- Node_type*&	GetTreeRootPtrRef(myRefClass& myRef)
								* Returns to the caller a reference-pointer to the root node.

							- vector<Example_type>&		GetExampleVec(myRefClass &myRef)
								* Returns to the caller a reference to the examples vector.

							- const vector<Case_type>&	GetCaseVec(const Example_type& ex)
								* Returns to the caller a reference to the vector of cases
								associated to an example.

	\par	
				It is recommened that the Adapter object not be itself templitized. 
				 A templitized Adapter has yet to be tested and it is feared by the 
				 Programmer that it would cause "nested teamplate" errors.

  

**	\par		GENERAL REMARKS:
**				C4.5 Tree building becomes more non-trival in the worst case with both 
**				 space and time as the number of cases increases. Adding more Classes will 
				 increase the complexity of the generated tree and bring it closer to the
				 worst case senerio.




**	\todo		At this time the DTrees are assuming that there are only two classes
**				 in the functions CalcInfo and CalcSplitInfo. Both functions are defined
**				 and declared in C45Generator.cpp.
**					
*/
////////////////////////////////////////////////////////////////////////////////
#pragma once
#include <algorithm>
#include <iostream>
#include <math.h>
#include <vector>
#include "node.hpp"



namespace DTree
{
	//!This flag value is set in the m_caseInfoGain vector for each case that is 
	//! considered as unneeded.
	const float IGNORE_CASE = -10000;
	
	////////////////////////////////////////////////////////////////////////////////
	/*!	\class		C45Generator
	**	\brief		Templitized class that is used to generate C4.5 DTrees.
	**	\param		RefObj_type			The type of object that this object will
	**									 will reference.
	**	\param		Adapter_type		The type of adapter that this object must
	**									 for C45Generator to properly interprete
	**									 data for this tree.
	**	\param		Node_type			Node_type typedef'd by Adapter.
	**	\param		Case_type			Case_type typedef'd by Adapter.
	**	\param		Class_type			Class_type typedef'd by Adapter.
	**	\param		Example_type		Example_type typedef'd by Adapter.
	**
	**	\author		Nate Cleveland
	**	\date		11/22/2002 1:21:51 PM
	**	\warning	Please refer to the file header of C45Generator.hpp for limitations
	**				 and requirments for Adapter_types.
	*/
	////////////////////////////////////////////////////////////////////////////////
	template<class RefObj_type, class Adapter, typename Node_type, typename Case_type, typename Class_type, typename Example_type>
	class C45Generator
	{
	public:
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Ctor for class. 
		**	\param		tree		Class that this module is to create a tree for.
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Simply saves a reference to the module it is to make a tree for.	
		**	\author		Nate Cleveland
		**	\date		11/14/2002 2:51:03 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		C45Generator(RefObj_type& tree, std::vector<Class_type>& classVec);

		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Dtor, does nothing at this time.
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Defined for future references.	
		**	\author		Nate Cleveland
		**	\date		11/14/2002 2:52:18 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		~C45Generator();

		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Creates a C45 tree.
		**	\param		none
		**	\return		none
		**	\exception	Reserves the right to throw an exception if there is a fatal error.
		**	\par		DESCRIPTION:
		**				Creates a tree based on the tenates of C45.	
		**	\author		Nate Cleveland
		**	\date		11/14/2002 2:54:04 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		void operator () (void) ;

	public:

		typedef std::vector<Example_type>			ExampleVector_type;
		typedef std::vector<Class_type>				ClassVector_type;
		typedef std::vector<Case_type>				CaseVector_type;

	protected:
		RefObj_type&			m_tree;				//!<reference to the c45 tree we are to grow.
		unsigned int			m_classNumber;		//!<Counts how many classes this data set has.
		std::vector<Class_type>	m_classVec;			//!<Vector of all possible classes in this tree.
		std::vector<float>		m_boundryVal;		//!<Break of point for each value.
		std::vector<float>		m_boundryLessCount;	//!<Count of how many values fall under the less equal
													//!< Boundry.
		std::vector<float>		m_caseGainVec;		//!<Vector of case gain values. A case will
													//!< be marked with a value of IGNORE_CASE if 
													//!< its data is of no use. m_caseGainVec is
													//!< gauranteed to be in the same order
													//!< as the attributes vectors.
		NodePredicate			m_nodePred;			//!<Holds the current node's predicate.
		std::vector<float>		m_classFreqVec;		//!<Vector filled with the frequency of each
													//!< class. Elements are in parralel order with
													//!< m_classVec.

		//Internal method used to build the tree.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Critical method that recursively builds the C45 tree.
		**	\param		examples	Vector of all examples to learn from.
		**	\param		node		Current node that we're on building this tree.
		**	\return		none
		**	\exception	Reserves the right to throw an exception if we are unable to 
		**				 generate this tree from the presented data.
		**	\par		DESCRIPTION:
		**				 Recursively builds a C45 tree based on the priciples of Nate
		**				  Cleveland (nclevela@digipen.edu) and J. Ross Quinlan.
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:33:44 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		void BuildTree(ExampleVector_type& examples, Node_type& node);


		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Calculates the frequency of all classes.
		**	\param		examples	Vector of all examples to learn from.
		**
		**	\return		Will return index to the most frequent Class.
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Calculates the sum of all classes from the given examples. Also
		**				  returns the index to the most frequent class.
		**	\author		Nate Cleveland
		**	\date		11/18/2002 4:17:32 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		unsigned int FindClassFreq(ExampleVector_type& examples) throw();


		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Returns to the caller the index to the largest m_caseGainVec member.
		**	\return		Index to the largest m_caseGainVec member. Will return -1 if there
		**				 are no applicable cases.
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Finds the index to the largest element in the m_caseGainVec 
		**				  member.
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:36:44 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		unsigned int FindCaseInfo_Best(void) const throw();
		
		

		// Calculates the info gains of all the cases. Stores the values in m_caseGainVec.
		//  Returns the index to the largest m_caseGainVec. Returns -1 if there are no
		//  applicable cases anymore.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Calculates the info gains of all the cases.
		**
		**	\param		classIndex		Index (in relation to the m_classVec member) of 
		**								 the class that the formula is to apply to this 
		**								 tree.
		**	\param		examples		Vector of examples to evaulate.
		**
		**	\return		Returns -1 if there are no applicable cases or index to the largest
		**				 m_caseGainVec member.
		**
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Calculates the info gains of all the cases. Stores the values in 
		**				  m_caseGainVec. Returns the index to the largest m_caseGainVec.
		**
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:39:07 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		unsigned int FindCaseInfo(unsigned int classIndex, ExampleVector_type& examples) throw();


		// Same as above, but only evaluates one case at a time and requires more parameters to 
		//  be passed. Also returns the value of the case rather than its index.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Calculates the info gains of a single case.
		**	\param		classIndex		Index of favored class.
		**	\param		caseIndex		Index of case we're evaluating.
		**	\param		caseBoundryVal	Value of the boundry posision.
		**	\param		examples		Vector of examples to evaulate.
		**	\return		Case info of evaluated case.
		**	\exception	none
		**	\par		DESCRIPTION:
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:41:17 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		float FindCaseInfo(unsigned int classIndex, unsigned int caseIndex, 
						   float caseBoundryVal, ExampleVector_type& examples) throw();

		//fills out all the internal boundry members.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Calculates the m_boundryVal and m_boundryLessCount members.
		**
		**	\param		classIndex		Index (in relation to the m_classVec member) of 
		**								 the class that the formula is to apply to this 
		**								 tree.
		**	\param		examples		Vector of examples to evaulate.
		**
		**	\return		none
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Fills out the m_boundryLessCount and m_boundryVal vectors. Will 
		**				  call the SelectBestBoundry() method to accomlish this.
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:30:50 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		void CalculateBoundries(unsigned int classIndex, ExampleVector_type& examples) throw();


		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Parses all cases and marks any that are found to be unneeded.
		**	\param		examples		Vector of examples to evaulate.
		**	\return		Returns the value of the recommended Predicate.
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Scans through the examples vector and examines all of the case 
		**				  sets. Clears the m_caseGainVec member and fills its members 
		**				  with either 0 or IGNORE_CASE. Ignore case will only be set if 
		**				  the case no longer can produce any information gain.
		**				  
		**	\par		 Also attempts to detect the special case of boolean true/false 
		**				  input values and will return the node "type" it recommends. 
		**				  This is done by calling the CheckPred method.
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:12:06 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		NodePredicate CaseParse(ExampleVector_type& examples);

		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Examine all of the examples and determines if this set of examples
		**				 is a boolean true/false predicate.
		**	\param		examples	Vector of examples to evaulate.
		**	\return		none
		**	\exception	none
		**	\par		DESCRIPTION:
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 4:21:13 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		static NodePredicate CheckPred(const ExampleVector_type& examples);

		//Takes a list of possible boundries and selects the best of them.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Returns the index, in relation the possibleBoundries vector, of 
		**				 Boundry that will provide the most information gain.
		**
		**	\param		classIndex			Index (in relation to the m_classVec member) 
		**									 of the class that the formula is to apply to 
		**									 this tree.
		**	\param		caseIndex			Index to the case in question.
		**	\param		possibleBoundries	Vector of all possible boundries.
		**	\param		examples			Vector of examples to evaulate.
		**
		**	\return		Returns the index, in relation to the possibleBoundries vector
		**				 of the best Boundry.
		**
		**	\exception	none
		**	\par		DESCRIPTION:
		**				 Analyzes all examples, cases and the passed in possibleBoundries
		**				  vector to find the best Boundry value for each case.
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:25:15 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		unsigned int SelectBestBoundry(unsigned int classIndex, unsigned int caseIndex, 
									   const std::vector<float>& possibleBoundries,
									   ExampleVector_type& examples) throw();

		//!Sets this node to a leaf and assigns to it the value of the most frequent class.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Sets this node as a leaf and assigns it the value of the most
		**				 frequent class.
		**	\param		node				The current node were on.
		**	\param		mostFrequentIndex	Index, in relation to the m_classVec member,
		**									 to the most common class.
		**	\return		none
		**	\exception	none
		**	\par		DESCRIPTION:
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:22:41 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
		void ChooseMostFrequent(Node_type& node, unsigned int mostFrequentIndex) throw();



		
		//////Follows are Depricated methods. Left so if needed they can be quickly
		//reincorperated.//////////////////////////////////////////////////////////

		//!Removes the relevent case from all the examples.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Will purge the relevent case from teh example set.
		**	\param		examples		Vector of examples to evaulate.		
		**	\param		indexToPurge	Index to the case, in relation to the attributes
		**								 vector inside each example, that is to be removed.
		**	\return		none
		**	\exception	none
		**	\par		DESCRIPTION:
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:21:08 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
//		void C45Generator::CasePurge(ExampleVector_type& examples, 
//									 unsigned int indexToPurge);

		//!Calculates the info gain for this tree in terms of the current favored class.
		////////////////////////////////////////////////////////////////////////////////
		//	FUNCTION:	
		/*!	\brief		Calculates the InfoGain of this tree.
		**	\param		classIndex		Index (in relation to the m_classVec member) of 
		**								 the class that the formula is to apply to this 
		**								 tree.
		**	\param		classFreq		Frequency of the afore mentioned class.
		**	\param		examples		Vector of examples to evaulate.
		**	\return		none
		**	\exception	none
		**	\par		DESCRIPTION:
		**					
		**	\author		Nate Cleveland
		**	\date		11/18/2002 5:17:31 PM
		**	\warning	none
		*/
		////////////////////////////////////////////////////////////////////////////////
//		float FindTreeInfoGain(unsigned int classIndex, float classFreq, 
//							   const ExampleVector_type& examples) throw();

	};//end C45Generator class

	/*!
	**	Since Visual C++ 6.0 does not support the export keyword we must use a hack around.
	**	 The hack is to #include the .cpp file. Ugly and evil, but it is the only option if
	**	 we wish to use a generic templitized method. If this file is ever included into a 
	**	 non-Visual C++ (or borland) workspace this hack should be removed and the 
	**	 keyword "export" added before each instance of the world "template" in 
	**	 C45Generator.cpp.
	*/
#	include "C45Generator.cpp"
}